---
title: "（70分 dp+贪心）倍数问题"
created: 2025-11-28
tags:
  - 算法
---

# （70分 dp+贪心）倍数问题

## 题目 [**倍数问题**](https://www.acwing.com/problem/content/description/1236/)

![[image-a7d6da0c.png]]

## 思路分析

![[image-6eacd9b2.png]]

首先第一感觉就是 优先选更大的数 从大到小 三层枚举

5/13

```typescript
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

LL a[N];

int n,m;

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    sort(a+1,a+n+1,greater<int>());

    for(int i=1;i<=n;i++){

        for(int j=i+1;j<=n;j++){

            for(int k=j+1;k<=n;k++){

                if((a[i]+a[j]+a[k])%m==0)

                    cout<<a[i]+a[j]+a[k];

                    return 0;

            }

        }

    }

    return 0;

}
```

![[image-de65d050.png]]

（不太理解为什么划在贪心里面 可能上面有个贪心策略从大的先选吧 其实做到那也就够了 往后写可能会错……起码有一半分）

再一看 好像是有限制的选择问题 且只能选一次 好像是01背包模型

![[image-1dbb717f.png]]

写不下去 它还有空间限制 三维dp数组实现不了

![[image-89244fce.png]]

换成vector动态分配能过几个

6/13

```typescript
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10, M=1010;

int n, m;

int a[N];

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++)

        scanf("%d", &a[i]);

    vector<vector<vector<int>>> f(n+1,vector<vector<int>> (4,vector<int>(m,-2e9)));

    for(int i=0;i<=n;i++)

        f[i][0][0]=0;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=3;j++)

            for(int k=0;k<m;k++)

                f[i][j][k]=max(f[i-1][j][k], f[i-1][j-1][((k-a[i])%m+m)%m]+a[i]);

    cout<<f[n][3][0];

    return 0;

}
```

![[image-6eacd9b2.png]]

很小丑 多过了一个数据

滚动数组把一维优化掉

8/13

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10, M=1010;

int n, m;

int a[N];

int f[5][M];

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++)

        scanf("%d", &a[i]);

    memset(f,-0x3f,sizeof f);

    f[0][0]=0;

    for(int i=1;i<=n;i++)

        for(int j=3;j>=1;j--)

            for(int k=0;k<m;k++)

                f[j][k]=max(f[j][k], f[j-1][((k-a[i])%m+m)%m]+a[i]);

    cout<<f[3][0];

    return 0;

}
```

![[image-27010def.png]]

感觉这里就是我的极限了……

后面只看限制 不看最大 又可以利用限制来进行贪心优化hh

几个数的和是否能整模k 在于它的余数而不在于它本身

同样的余数 只需要保留最大的三个即可

范围大大缩小……

写不来

![[image-79696784.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10, M=1010;

int n, m;

vector<int> a[N];

int f[5][M];

int main()

{

    cin>>n>>m;

    for(int i=0;i<n;i++){

        int x;cin>>x;

        a[x%m].push_back(x);

    }

    memset(f,-0x3f,sizeof f);

    f[0][0]=0;

    for(int i=0;i<m;i++){

        sort(a[i].begin(),a[i].end());

        reverse(a[i].begin(),a[i].end());

        for(int u=0;u<3 && u<a[i].size();u++){

            int x=a[i][u];

            for(int j=3;j>=1;j--){

                for(int k=0;k<m;k++){

                    f[j][k]=max(f[j][k], f[j-1][((k-x)%m+m)%m]+x);

                }

            }

        }

    }

    cout<<f[3][0];

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/贪心相关模型/疑难杂类/（50分 多路归并 二分）技能升级|（50分 多路归并 二分）技能升级]] 🏠 [[00-刷题理模型]] ➡️ [[（归并 逆序对性质）小朋友排队|（归并 逆序对性质）小朋友排队]]